<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
           给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
           输入：text1 = "abcde", text2 = "ace" 
           输出：3
           解释：最长公共子序列是 "ace" ，它的长度为 3 。

           分析：和最长递增子序列有点像，只是这个是比字符串是否相等，又和最长重复子数组有点像;
           找相似点？

           dp[i][j]含义：从0->i-1的text1字符串和从0->j-1的text2的最长公共子序列的长度，记住这里是i-1和j-1，所以比较的时候索引是text1[i-1]和text[j-1]
           初始化：dp[i][0]应该初始化为0，因为从0->i-1的text1和空字符的最长公共子序列长度就是''就是0，dp[0][j]也应该都是0
           遍历顺序：从前往后遍历
           递推公式：如果text1[i - 1] === text2[j - 1]，则dp[i][j] = dp[i - 1][j - 1]
                    如果不相等，则dp[i][j] = Math.max(dp[i][j - 1], dp[j][i -1])
        */
        /* 
            时间：O(n * m)
            空间：O(n * m)
        */
        var longestCommonSubsequence = function(text1, text2) {
            let len1 = text1.length;
            let len2 = text2.length;
            let dp = new Array(len1 + 1).fill(0).map(() => new Array(len2 + 1).fill(0));
            // dp[i][0]和dp[0][j]都是0，因为text1从0 -> i-1字符串和''空字符串的公共子序列都是0，dp[i][0]的j是0，意味是这个比较的text2的就是空字符串，思考dp数组的定义就能够得出
            // 需要双重for循环
            for (let i = 1; i <= len1; i++) {
                // j需要倒序,倒序的原因是：1. dp[j]需要从上一轮的dp[j - 1]推导出来 2. 正序，可能dp[j - 1]在这一轮又被用了一次
                for (let j = 1; j <= len2; j++) {
                    if (text1[i - 1] === text2[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1] + 1
                    } else {
                        dp[i][j] = Math.max(dp[i][j - 1], dp[i -1][j])
                    }
                }
            }
            console.log(dp, 'dp');
            return dp[len1][len2]
        };
        // console.log(longestCommonSubsequence('abcde', 'ace'));
        console.log(longestCommonSubsequence('abcde', 'ae'));
        // console.log(findLength([0,0,0,0,0], [0,0,0,0,0]));
    </script>
</body>

</html>